\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx} 
\usepackage[left=1cm,right=1cm,top=1cm,bottom=2cm]{geometry}
\title{NumPDE Homework 6}
\author{Jiang Zhou 3220101339}
\date{2025/5/7}

\begin{document}
\maketitle
\section{Exercise 11.81}
The classical fourth-order $\mathbf{RK}$ method is an $\mathbf{ERK}$ method of the form:
\begin{equation*}
    \begin{cases}
        y_1 = f(u(t_n), t_n)\\
        y_2 = f(u(t_n)+\frac{k}{2}y_1, t_n + \frac{k}{2})\\
        y_3 = f(u(t_n)+\frac{k}{2}y_2, t_n+\frac{k}{2})\\
        y_4 = f(u(t_n)+ky_3, t_n+k)\\
        u(t_{n+1}) = u(t_n) + \frac{k}{6}(y_1+2y_2+2y_3+y_4).
    \end{cases}
\end{equation*}
The classical fourth-order $\mathbf{RK}$ method with Butcher tableau:
\[
\begin{array}{c|cccc}
    0 & \\
    \frac{1}{2} & \frac{1}{2} \\
    \frac{1}{2} & 0 & \frac{1}{2} \\
    1 & 0 & 0 & 1 \\
    \hline
    & \frac{1}{6} & \frac{1}{3} & \frac{1}{3} & \frac{1}{6} \\
\end{array}        
\]
\subsection{Compute \(B(p)\):}
\begin{align*}
    \sum_{j=1}^4 b_j c_j^{1-1} &= \sum_{j=1}^4 b_j = 1,\\
    \sum_{j=1}^4 b_j c_j^{2-1} &= \sum_{j=1}^4 b_j c_j = 0 + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = \frac{1}{2},\\
    \sum_{j=1}^4 b_j c_j^{3-1} &= \sum_{j=1}^4 b_j c_j^2 = 0 +  \frac{1}{12} + \frac{1}{12} + \frac{1}{6} = \frac{1}{3},\\
    \sum_{j=1}^4 b_j c_j^{4-1} &= \sum_{j=1}^4 b_j c_j^3 = 0 + \frac{1}{24} + \frac{1}{24} + \frac{1}{6} = \frac{1}{4},\\
    \sum_{j=1}^4 b_j c_j^{5-1} &= \sum_{j=1}^4 b_j c_j^4 = 0 + \frac{1}{48} + \frac{1}{48} + \frac{1}{6} = \frac{5}{24} \neq \frac{1}{5}.
\end{align*}
As a result, \(p = 4\).
\subsection{Compute \(C(\eta)\):}
\begin{align*}
    \sum_{j=1}^{4} a_{i,j} c_j^{1-1} &= \sum_{j=1}^{4} a_{i,j} = c_i,\\
    \sum_{j=1}^{4} a_{1,j} c_j^{2-1} &= \sum_{j=1}^{4} a_{1,j} c_j = 0 = \frac{c_1^2}{2},\\
    \sum_{j=1}^{4} a_{2,j} c_j^{2-1} &= \sum_{j=1}^{4} a_{2,j} c_j = 0 \neq \frac{c_2^2}{2}.
\end{align*}
Thus \(C(1)\) is satisfied.

\subsection{Compute \(D(\zeta)\):}
\begin{align*}
    \sum_{j=1}^{4} b_j c_j^{1-1} a_{j,1} &= \sum_{j=1}^{4} b_j a_{j,1} = \frac{1}{6} = b_1(1-c_1) = 1/6\\
    \sum_{j=1}^{4} b_j c_j^{1-1} a_{j,2} &= \sum_{j=1}^{4} b_j a_{j,2} = \frac{1}{6} = b_2(1-c_2) = 1/6\\
    \sum_{j=1}^{4} b_j c_j^{1-1} a_{j,3} &= \sum_{j=1}^{4} b_j a_{j,3} = \frac{1}{6} = b_3(1-c_3) = 1/6\\
    \sum_{j=1}^{4} b_j c_j^{1-1} a_{j,4} &= \sum_{j=1}^{4} b_j a_{j,4} = 0 = b_4(1-c_4) = 0\\
\end{align*}
\begin{align*}
    \sum_{j=1}^{4} b_j c_j^{2-1} a_{j,1} &= \sum_{j=1}^{4} b_j c_j a_{j,1} = \frac{1}{12} = \frac{b_1}{2}(1-c_1^2) = 1/12\\
    \sum_{j=1}^{4} b_j c_j^{2-1} a_{j,2} &= \sum_{j=1}^{4} b_j c_j a_{j,2} = \frac{1}{12} = \frac{b_2}{2}(1-c_2^2) = 1/12\\
    \sum_{j=1}^{4} b_j c_j^{2-1} a_{j,3} &= \sum_{j=1}^{4} b_j c_j a_{j,3} = \frac{1}{6} = \frac{b_3}{2}(1-c_3^2) = 1/6\\
    \sum_{j=1}^{4} b_j c_j^{2-1} a_{j,4} &= \sum_{j=1}^{4} b_j c_j a_{j,4} = 0 = \frac{b_4}{2}(1-c_4^2) = 0\\
\end{align*}
Thus \(\zeta = 2\).\\
Applying Lemma 11.66 to \(p=4, \eta = 3, \zeta = 2\), we can get that the method has order of accuracy at least \boxed{4}.



\section{Exercise 11.87}
The RK4 method is represented by the following Butcher tableau:
\[
\begin{array}{c|cccc}
0 & \\
\frac{1}{2} & \frac{1}{2} \\
\frac{1}{2} & 0 & \frac{1}{2} \\
1 & 0 & 0 & 1 \\
\hline
& \frac{1}{6} & \frac{1}{3} & \frac{1}{3} & \frac{1}{6} \\
\end{array}
\]
The stability function \( R(z) \) for a Runge-Kutta method is given by:
\[
R(z) = 1 + z \mathbf{b}^T (I - z \mathbf{A})^{-1} \mathbf{1},
\]
First, compute \( I - z \mathbf{A} \):
\[
I - z \mathbf{A} = \begin{bmatrix}
1 & 0 & 0 & 0 \\
-\frac{z}{2} & 1 & 0 & 0 \\
0 & -\frac{z}{2} & 1 & 0 \\
0 & 0 & -z & 1 \\
\end{bmatrix}
\]
The inverse \( (I - z \mathbf{A})^{-1} \) is computed as:
\[
(I - z \mathbf{A})^{-1} = \begin{bmatrix}
1 & 0 & 0 & 0 \\
\frac{z}{2} & 1 & 0 & 0 \\
\frac{z^2}{4} & \frac{z}{2} & 1 & 0 \\
\frac{z^3}{4} & \frac{z^2}{2} & z & 1 \\
\end{bmatrix}
\]
Multiply \( \mathbf{b}^T \) with \( (I - z \mathbf{A})^{-1} \mathbf{1} \):
\[
(I - z \mathbf{A})^{-1} \mathbf{1} = \begin{bmatrix}
1 \\
1 + \frac{z}{2} \\
1 + \frac{z}{2} + \frac{z^2}{4} \\
1 + \frac{z}{2} + \frac{z^2}{2} + \frac{z^3}{4} \\
\end{bmatrix}
\]
Now, multiply by \( \mathbf{b}^T \):
\[
\mathbf{b}^T (I - z \mathbf{A})^{-1} \mathbf{1} = \frac{1}{6} \cdot 1 + \frac{1}{3} \left(1 + \frac{z}{2}\right) + \frac{1}{3} \left(1 + \frac{z}{2} + \frac{z^2}{4}\right) + \frac{1}{6} \left(1 + \frac{z}{2} + \frac{z^2}{2} + \frac{z^3}{4}\right).
\]
Simplify:
\[
= \frac{1}{6} + \frac{1}{3} + \frac{1}{3} + \frac{1}{6} + \left(\frac{1}{6} + \frac{1}{6} + \frac{1}{12}\right) z + \left(\frac{1}{12} + \frac{1}{12}\right) z^2 + \frac{1}{24} z^3
\]
\[
= 1 + \frac{z}{2} + \frac{z^2}{6} + \frac{z^3}{24}.
\]
The stability function of the classical RK4 method is:
\[
\boxed{R(z) = 1 + z + \frac{z^2}{2} + \frac{z^3}{6} + \frac{z^4}{24}}
\]
\section{Exercise 11.91}
For \(s=1, |R_1(z)| = |1+z| \leq 1\).\\
\(\forall z \in S_1, |1+z| \leq 1.\) Then we apply the condition into \(|R_2(z)| = |1+z+\frac{z^2}{2}|\):
\begin{align*}
    |R_2(z)| = |1+z+\frac{z^2}{2}| = |\frac{1}{2} + \frac{1}{2}(z+1)^2| \leq \frac{1}{2} + \frac{1}{2}|(z+1)^2| \leq \frac{1}{2} + \frac{1}{2} \times 1 = 1.
\end{align*}
As a result \(S_1 \subset S_2\).
Now consider \( s = 3 \):\\
Assume \(z = a+bi\), \(\forall z \in S_2, |1+z+\frac{1}{2}z^2| \leq 1.\) We can get:
\begin{align*}
    1+z+\frac{1}{2}z^2 = 1+a+bi+\frac{1}{2}(a^2-b^2+2abi) = 1+a+\frac{a^2-b^2}{2}+(b+ab)i;\\
    |1+z+\frac{1}{2}z^2|^2 = |1+a+\frac{a^2-b^2}{2}+(b+ab)i|^2 = (1+a+\frac{a^2-b^2}{2})^2+(b+ab)^2\\
    2a+2a^2+a^3+\frac{a^4}{4}-b^2+ab^2+\frac{a^2b^2}{2}+\frac{5}{4}b^4\\
\end{align*}
As shown in Figure \ref{fig:E11_91}, \(S_2 \subset S_3\)
As shown in Figure \ref{fig:E11_91}, this does not hold for ERK methods with a higher stage.
\begin{figure}[!ht]
    \centering
    \includegraphics[width=0.5\textwidth]{figure/E11_91.png}
    \caption{Stability regions of explicit RK methods}
    \label{fig:E11_91} 
\end{figure}


\section{Exercise 11.97}
An $\mathbf{RK}$ method is A-stable yields:
\[
  |R(z)| \leq 1 \quad \forall \quad \text{Re}(z) \leq 0.
\]
Assume \( R(z) = \frac{P(z)}{Q(z)} \), where:
\[
P(z) = \sum_{i=0}^m p_i z^i, \quad Q(z) = \sum_{i=0}^n q_i z^i, \quad p_m \neq 0, q_n \neq 0.
\]
So we can get:
\begin{equation*}
    R(z) = \frac{P(z)}{Q(z)} = 
    \begin{cases}
        0, \text{if}\quad m < n\\
        \frac{p_m}{q_n}, \text{if}\quad m = n\\
        \infty, \text{if}\quad m > n.
    \end{cases}
\end{equation*}
If the $\mathbf{RK}$ method is L-stable, \(\lim_{z\to \infty} R(z) = 0\). By the defintion, we can get \(\deg Q(z) > \deg P(z)\).\\
If \(\deg Q(z) > \deg P(z)\), \(\lim_{z\to \infty} R(z) = 0\). Due to the $\mathbf{RK}$ method is A-stable, we can get the $\mathbf{RK}$ method is L-stable.

\section{Exercise 11.100}
\begin{align*}
    \lim_{z\to \infty} R(z) &= \lim_{z\to \infty} (1+z\mathbf{b}^T(I - zA)^{-1}\mathbf{1}) \\
    &= 1+\lim_{z\to \infty}\mathbf{b}^T(\frac{1}{z}I - A)^{-1}\mathbf{1}\\
    &= 1-\mathbf{b}^TA^{-1}\mathbf{1}
\end{align*}
Due to $A$ satisfies (11.76), we can get:
\begin{align*}
    A\mathbf{e}_1 = b_1\mathbf{1}.
\end{align*}
where \(\mathbf{e}_1 = (1,0,0\ldots0)^T\).\\
\begin{align*}
    \lim_{z\to \infty} R(z)= 1-\mathbf{b}^TA^{-1}\mathbf{1} = 1-\frac{1}{b_1}\mathbf{b}^T\mathbf{e}_1 = 1-\frac{b_1}{b_1} = 0.
\end{align*}
Besides the $\mathbf{RK}$ method is A-stable, the method is L-stable.

\section{Exercise 11.105}
\subsection*{(1)}
\begin{align*}
    B(p): & \quad \sum_{i=1}^{s} b_i c_i^{k-1} = \frac{1}{k}, \quad k=1,\dots,5 \\
    C(\eta): & \quad \sum_{j=1}^{s} a_{ij} c_j^{k-1} = \frac{c_i^k}{k}, \quad i=1,\dots,s,\; k=1,\dots,2 \\
    D(\zeta): & \quad \sum_{i=1}^{s} b_i c_i^{k-1} a_{ij} = \frac{b_j(1-c_j^k)}{k}, \quad j=1,\dots,s,\; k=1,\dots,2\\
    p = 5, \eta = 2, \zeta = 2.
\end{align*}
where $\eta+\zeta+1\geq p, p\leq 2\eta+2$ for order $p=5$.

\subsection*{(2)}
\subsubsection*{(i)}
As shown in Figure \ref*{fig:E11_105_2}, the method is L-stable.
\begin{figure}[!ht]
    \centering
    \includegraphics[width=0.5\textwidth]{figure/E11_105_2.png}
    \caption{Stability functuon $|R(yi)|$}
    \label{fig:E11_105_2} 
\end{figure}

\subsubsection*{(ii)}
As shown in Figure \ref*{fig:E11_105_1}, the poles of \(R(z)\) are \(3.6378, 2.6811 - 3.0504i, 2.6811 + 3.0504i\), all reside at the open right half-plane.\\
\begin{figure}[!ht]
    \centering
    \includegraphics[width=1\textwidth]{figure/E11_105_1.png}
    \caption{Poles of \(R(z)\)}
    \label{fig:E11_105_1} 
\end{figure}
As a result, the method is A-stable.\\
Due to the method is A-stable and \(\forall j = 1,2,3,\quad a_{3,j} = b_j\), the method is L-stable by Theorem 11.99.

\section{Exercise 11.114}
The implicit midpoint method is given by:
\[ U^{n+1} = U^n + kf \left( \frac{U^n + U^{n+1}}{2}, t_n + \frac{k}{2} \right) \]

To write this in the standard form (11.20) of a Runge-Kutta method, we get that the standard form is:
\begin{equation*}
    \begin{cases}
        \mathbf{y}_1 = \mathbf{f}(\mathbf{U}^n, t_n),\\
        \mathbf{y}_2 = \mathbf{f}(\mathbf{U}^n + k\mathbf{y}_1 - \frac{k}{2}\mathbf{y}_2, t_n+\frac{k}{2}),\\
        \mathbf{U}^{n+1} = \mathbf{U}^n + k\mathbf{y}_2  
    \end{cases}
\end{equation*}

The Butcher tableau for the implicit midpoint method is:

\[
\begin{array}{c|cc}
c & A \\
\hline
 & b^T \\
\end{array}
=
\begin{array}{c|cc}
0 & 0 & 0\\
\frac{1}{2} & 1 & -\frac{1}{2}\\
\hline
 & 0 &1 \\
\end{array}
\]
Because the matrix $A$ is negative semi-definite, the system is contractive. So the $\mathbf{f}$ satisfies the one-sided Lipschitz condition\\
Consider two solutions $U^n$ and $V^n$ and their updates via the implicit midpoint method:
\[ U^{n+1} = U^n + k f\left(\frac{U^n + U^{n+1}}{2}, t_n+\frac{k}{2}\right) \]
\[ V^{n+1} = V^n + k f\left(\frac{V^n + V^{n+1}}{2}, t_n+\frac{k}{2}\right) \]
Subtract the two equations:
\[ U^{n+1} - V^{n+1} = U^n - V^n + k \left[f\left(\frac{U^n + U^{n+1}}{2}, t_n+\frac{k}{2}\right) - f\left(\frac{V^n + V^{n+1}}{2}, t_n+\frac{k}{2}\right)\right] \]
Take the inner product with $\frac{(U^{n+1} - V^{n+1}) + (U^n - V^n)}{2}$:
\begin{align*}
    &\left\langle \frac{U^{n+1} - V^{n+1} + U^n - V^n}{2}, U^{n+1} - V^{n+1} - (U^n - V^n) \right\rangle \\
    &= k \left\langle \frac{U^{n+1} - V^{n+1} + U^n - V^n}{2}, f\left(\frac{U^n + U^{n+1}}{2}, t_n+\frac{k}{2}\right) - f\left(\frac{V^n + V^{n+1}}{2}, t_n+\frac{k}{2}\right) \right\rangle
\end{align*}
The left side simplifies to:
\[ \frac{1}{2}\|U^{n+1} - V^{n+1}\|^2 - \frac{1}{2}\|U^n - V^n\|^2 \]
By the one-sided Lipschitz condition (with Lipschitz constant $L \leq 0$):
\[ \left\langle \frac{U^{n+1} - V^{n+1} + U^n - V^n}{2}, f\left(\frac{U^n + U^{n+1}}{2}, t_n+\frac{k}{2}\right) - f\left(\frac{V^n + V^{n+1}}{2}, t_n+\frac{k}{2}\right) \right\rangle \leq L \left\|\frac{U^{n+1} - V^{n+1} + U^n - V^n}{2}\right\|^2 \leq 0 \]
Therefore:
\begin{align*}
    \frac{1}{2}\|U^{n+1} - V^{n+1}\|^2 - \frac{1}{2}\|U^n - V^n\|^2 &\leq 0 \\
    \|U^{n+1} - V^{n+1}\| &\leq \|U^n - V^n\|
\end{align*}

\end{document}
